package lib

import (
	"math"
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         272,
		Discription: "二叉搜索树中最接近指定值的k个数",
		Level:       2,
		Labels: map[string]int{
			"二叉搜索树": 1,
			"二叉树":   1,
			"滑动窗口":  1,
		},
	})
}

func ClosestKValues(root *ds.TreeNode, target float64, k int) []int {
	s := make([]*ds.TreeNode, 0)
	cur := root
	res := make([]int, 0)
	for cur != nil || len(s) > 0 {
		for cur != nil {
			s = append(s, cur)
			cur = cur.Left
		}

		top := s[len(s)-1]
		s = s[:len(s)-1]
		if len(res) < k {
			res = append(res, top.Val)
		} else {
			if math.Abs(float64(top.Val)-target) < math.Abs(float64(res[0])-target) {
				res = append(res, top.Val)
				res = res[1:]
			} else {
				break
			}
		}

		cur = top.Right
	}

	return res
}
